package huawei;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 接雨水
 *
 * @Author Jun jie Yi
 * 2022/4/4 14:32
 */

public class LoadRain {
    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int trap = trap2(height);
        System.out.println(trap);
        Arrays.stream(height).max().getAsInt();
        List<Integer> aa = new ArrayList<>();
        aa.add(9);
        aa.add(2);
        aa.add(3);
        Integer integer = aa.stream().max(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 > o2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        }).get();
        System.out.println(integer);
    }

    //击败了 5.50%
    public static int trap(int[] height) {
        int ans = 0;
        int size = height.length;
        for (int i = 1; i < size - 1; i++) {
            int max_left = 0, max_right = 0;
            for (int j = i; j >= 0; j--) { //Search the left part for max bar size
                max_left = Math.max(max_left, height[j]);
            }
            for (int j = i; j < size; j++) { //Search the right part for max bar size
                max_right = Math.max(max_right, height[j]);
            }
            ans += Math.min(max_left, max_right) - height[i];
        }
        return ans;
    }

    //必须要将空间削平 击败了 11.50%(我所作)
    public static int trap1(int[] height) {
        int i = 0, sum = 0;
        while (i < height.length) {
            int flag_location = 0;
            //跳格运算
            if (height[i] > 0) {
                //判断从后往左是否有比他大的
                int max = 0, flag = 0;
                for (int j = height.length - 1; j > i; j--) {
                    //找到最大的
                    if (max < height[j]) {
                        max = height[j];
                    }
                    if (height[j] >= height[i]) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) {
                    height[i] = max;//削峰
                }
                for (int j = i + 1; j < height.length; j++) {
                    //形成方块空间
                    if (height[j] >= height[i]) {
                        int area = (j - i) * height[i];//长方形的面积
                        //减去他黑色部分的面积
                        for (int k = i; k < j; k++) {
                            if (height[k] > 0) {
                                area = area - height[k];
                            }
                        }
                        sum = sum + area;
                        i = j;
                        flag_location = 1;
                        break;
                    }
                }
            }
            if (flag_location == 1) continue;
            i++;
        }
        return sum;
    }

    //双指针
    public static int trap2(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n - 1;
        int leftMax = height[0];
        int rightMax = height[n - 1];
        //存储结果
        int sum = 0;
        while (left != right) {
            if (leftMax < rightMax) {//高度对比，左边的是否比右边的低
                sum += (leftMax - height[left]);
                left++;
            } else {
                sum += (rightMax - height[right]);
                right--;
            }
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
        }
        return sum;
    }
}
